package com.cloud.code.算法.排序.快速排序;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {2, 1, 4, 2, 5, 7, 3};

        sort(arr,0,arr.length-1);

        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr, int l, int r) {

        if(l >= r){
            return;
        }

        int p = partition(arr,l,r);
        sort(arr,l,p);
        sort(arr,p+1,r);
    }

    private static int partition(int[] arr, int l, int r) {
        //这里我们选取l 第一个元素为标定点
        int j = l;
        for (int i = l+1; i <= r; i++) {
            if(arr[i]<arr[l]){
                j++;
                swap(arr,i,j);
            }
        }
        swap(arr,j,l);

        return j;
    }

    private static void swap(int[] arr, int i, int j) {
        int e = arr[i];
        arr[i] = arr[j];
        arr[j] = e;
    }
}
